package leetcode.editor.offer;

// 剑指 Offer 11. 旋转数组的最小数字
// https://blog.algomooc.com/011.html#%E4%B8%80%E3%80%81%E9%A2%98%E7%9B%AE%E6%8F%8F%E8%BF%B0
class XuanZhuanShuZuDeZuiXiaoShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new XuanZhuanShuZuDeZuiXiaoShuZiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 二分法
         *
         * @param numbers
         * @return
         */
        public int minArray(int[] numbers) {
            int left = 0;
            int right = numbers.length - 1;
            while (left <= right) {
                int mid = (left + right) / 2;
                if (numbers[mid] > numbers[right]) {
                    left = mid + 1;
                } else if (numbers[mid] < numbers[right]) {
                    // 注意包括的是mid，所以不是mid - 1
                    right = mid;
                } else if (numbers[mid] == numbers[right]) {
                    // right = right - 1;
                    // 也可以用线性查找代替二分查找
                    // 例如对于数组 {1,1,1,0,1}，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间
                    int x = left;
                    for (int i = left + 1; i < right; i++) {
                        if (numbers[i] < numbers[x]) x = i;
                    }
                    return numbers[x];
                }
            }
            return numbers[left];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
